// 2025/10/22
// 被围绕的区域

class Solution {
public:
    vector<pair<int, int>> dpos = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    void dfs(vector<vector<char>>& board, vector<vector<bool>>& isVisited, int i, int j)
    {
        int m = board.size(), n = board[0].size();
        auto isValid = [m, n, &isVisited](int x, int y){
            return (0 <= x && x < m && 0 <= y && y < n);
        };
        isVisited[i][j] = true;
        for(auto pr : dpos)
        {
            int x = i + pr.first, y = j + pr.second;
            if(isValid(x, y) && !isVisited[x][y] && board[x][y] == 'O')
            {
                dfs(board, isVisited, x, y);
            }
        }
    }

    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> isVisited(m, vector<bool>(n, false));
        for(int i = 0; i < m; i++)
        {
            if(!isVisited[i][0] && board[i][0] == 'O')
                dfs(board, isVisited, i, 0);
            if(!isVisited[i][n - 1] && board[i][n - 1] == 'O')
                dfs(board, isVisited, i, n - 1);
        }

        for(int j = 1; j < n - 1; j++)
        {
            if(!isVisited[0][j] && board[0][j] == 'O')
                dfs(board, isVisited, 0, j);
            if(!isVisited[m - 1][j] && board[m - 1][j] == 'O')
                dfs(board, isVisited, m - 1, j);
        }

        for(int i = 1; i < m - 1; i++)
        {
            for(int j = 1; j < n - 1; j++)
            {
                if(!isVisited[i][j] && board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
};